package easy;

import common.Node;

/**
 * 链表反转
 *
 * @author WangChenyu
 * @since 2024-04-15 13:59
 */
public class LinkedReversal {

    /**
     * 迭代法，流程：<br/>
     * ①记录cur的后续链表,next = cur.next <br/>
     * ②将cur->next指向改为cur->pre, <br/>
     * ③将pre改为cur <br/>
     * ④将cur改为next <br/>
     *
     * @param node
     * @param <T>
     * @return
     */
    public static <T> Node<T> linkedReversal(Node<T> node) {
        if (node == null || node.next == null) {
            return node;
        }
        Node<T> pre = null;
        while (node != null) {
            Node<T> next = node.next;
            node.next = pre;// 反转
            pre = node; // 移动
            node = next;
        }
        return pre;
    }

    /**
     * 头插法
     * @param head
     * @return
     * @param <T>
     */
    public static <T> Node<T> linkedReversal2(Node<T> head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node<T> newHead = null, tmp;
        while (head != null){
            tmp = head;
            head = head.next;
            tmp.next = newHead;
            newHead = tmp;
        }

        return newHead;
    }

    public static void main(String[] args) {
        Node<Integer> node0 = new Node<>(0, null);
        Node<Integer> node1 = new Node<>(1, node0);
        Node<Integer> node2 = new Node<>(2, node1);
        Node<Integer> node3 = new Node<>(3, node2);
        Node<Integer> node4 = new Node<>(4, node3);
        Node<Integer> node5 = new Node<>(5, node4);
        Node<Integer> node6 = new Node<>(6, node5);
        Node<Integer> node7 = new Node<>(7, node6);
        System.out.println(linkedReversal(node7));
    }
}
